package demo4;

import javax.swing.tree.TreeNode;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:二叉树的最近公共祖先第二种方法
 * User: liangyuanzhang
 * Date: 2025-4-27
 * Time: 23:25
 */
/*

 */
public class Test {
    //1.这个方法是获取路径上的所有节点
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if (root == null){
            return false;
        }
        stack.push(root);//这一步就是路径的获取，如果不为空直接入栈
        if (root == node){//入栈后如果等于要找的节点，直接返回true
            return true;
        }
        //到这里之后就可以开始递归(相当于前序遍历)
        boolean ret = getPath(root.left,node,stack);
        if (ret == true){
            return true;
        }
        ret = getPath(root.right,node,stack);
        if (ret == true){
            return true;
        }
        stack.pop();
        return false;
    }

    //2.这个方法是比较两个栈的大小，大的出size个
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //要有两个栈
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);//这里执行完成之后两个路径就有了

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if (sizeP > sizeQ){
            int size = sizeP - sizeQ;
            while (size != 0){
                stackP.pop();
                size--;
            }
        }else{
            int size = sizeQ - sizeP;
            while (size != 0){
                stackQ.pop();
                size--;
            }
        }

        //3.到这里之后两个栈的个数一样，同时判断两个栈的栈顶元素一不一样，一样就返回栈顶元素
        //不一样就同时弹出
        while(!stackP.isEmpty()){
            if (stackP.peek() == stackQ.peek()){
                return stackP.peek();
            }else{
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;


    }

}
